//aa
public class LCS {

	public int doLCS(String s1, String s2) {
		final int len1 = s1.length();
		final int len2 = s2.length();
		int[][] lcs = new int[len1 + 1][len2 + 1];
		for(int i = 0 ; i <= len1 ; i ++) {
			lcs[i][0] = 0;
		}
		for(int i = 0 ; i <= len2 ; i ++) {
			lcs[0][i] = 0;
		}
		for(int i = 1 ; i <= len1 ; i ++) 
			for (int j = 1 ; j <= len2 ; j++) {
				if(s1.charAt(i-1) == s2.charAt(j-1)) {
					lcs[i][j] = lcs[i-1][j-1] + 1;
				}
				else
					lcs[i][j] = Math.max(lcs[i][j-1], lcs[i-1][j]);
			}
		return lcs[len1][len2];
	}
	
}
